package everydayGrade.t2;

/**
 * @Author: Siantar
 * @Date: 2023-11-13-16:09
 * @Description: 1.0
 */
public class T0307 {

    class NumArray {

        public NumArray(int[] nums) {
            N=nums.length;
            for (int i = 0; i < N; i++) {
                update(root,0,N,i,i,nums[i]);
            }
        }

        public void update(int index, int val) {
            update(root,0,N,index,index,val);
        }

        public int sumRange(int left, int right) {
            return query(root,0,N,left,right);
        }


        class Node {
            Node left;
            Node right;
            int value;
            int change;
        }

        public Node root = new Node();
        public int N = (int) 1e9;

        public void update(Node node, int start, int end, int left, int right, int change) {
            if (left <= start && end <= right) {
                node.value = (end - start + 1) * change;
                node.change = change;
                return;
            }
            int mid = start + ((end - start) >> 1);
            pushDown(node, mid - start + 1, end - mid);
            if (left <= mid) update(node.left, start, mid, left, right, change);
            if (mid < right) update(node.right, mid + 1, end, left, right, change);
            pushUp(node);
        }

        public int query(Node node, int start, int end, int left, int right) {
            if (left <= start && end <= right) {
                return node.value;
            }
            int mid = start + ((end - start) >> 1), ans = 0;
            pushDown(node, mid - start + 1, end - mid);
            if (left <= mid) ans += query(node.left, start, mid, left, right);
            if (mid < right) ans += query(node.right, mid + 1, end, left, right);
            return ans;
        }


        public void pushUp(Node node) {
            node.value = node.left.value + node.right.value;
        }

        public void pushDown(Node node, int leftNum, int rightNum) {
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.change == 0) return;
            node.left.value = node.change * leftNum;
            node.right.value = node.change * rightNum;
            node.left.change = node.change;
            node.right.change = node.change;
            node.change = 0;
        }

    }
}
